#pragma once
#include <Windows.h>
#include <list>
#include <map>
#include <string>
#include <string.h>

#ifndef max 
#define max(a,b) (((a) > (b)) ? (a) : (b)) 
#endif 

#ifndef min 
#define min(a,b) (((a) < (b)) ? (a) : (b)) 
#endif



// ============================================================================
// CLASS STRING::unicode, utf8, ansi
// some agile string classes with format conversion and hand-over features.
// hand-over feature means passing buffer pointer to another instance, and the 
// data will be released by the new instance.
// ============================================================================
namespace STRING
{
    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: is_space()
    // check a char is a space char or not.
    ///////////////////////////////////////////////////////////////////////////
    template <typename TC>
    inline bool is_space(const TC t)
    {
        return (t == 0x20 || t == 0x09 || t == 0x0a || t == 0x0d);
    }


    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: length()
    // get length of a string.
    // e.g.: a="123456"; length(a)="6"
    ///////////////////////////////////////////////////////////////////////////
    template <typename T>
    inline int  length(const T* t)
    {
        if(!t) return 0; 
        T* p = (T*)t; 
        while(*p != 0x00) {p++;} 
        return (p-t); 
    }


    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: substr()
    // get sub string of a string.
    // e.g.: a="123456"; substr(a, 1, 2)="23"
    ///////////////////////////////////////////////////////////////////////////
    template <typename T>
    inline T substr(T& str, int n, int len = -1)
    {
        int begin = max(n, 0);
        int sublen = min(str.length(), n + len) - begin;
        if(len < 0) sublen = str.length() - n;

        if(sublen <= 0)
        {
            return T(0);
        }

        T tmp(sublen);
        for(int i = 0; i < sublen; ++i)
        {
            tmp[i] = str[begin+i];
        }
        return tmp;
    }


    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: trim()
    // get rid of the invisible characters(space, tab, CR, LF, etc.) at the 
    // begining or at the end of the string.
    // e.g.: a=" \t 123 456   \r\n"; trim(a)="123 456"
    ///////////////////////////////////////////////////////////////////////////
    template <typename T>
    inline T& trim(T& str)
    {
        if(str.is_null())
        {
            return str;
        }

        int begin, end;
        for(end = str.length() - 1; end >= 0; end--)
        {
            if(str[end] > 0x20 || str[end] < 0)
            {
                break;
            }
        }

        for(begin = 0; begin < end; ++begin)
        {
            if(str[begin] > 0x20 || str[begin] < 0)
            {
                break;
            }
        }

        if(begin > 0 && end >= begin)
        {
            memmove(*str, *str + begin, (end - begin + 1) * sizeof(**str));
        }
        str[end >= begin ? (end - begin + 1) : 0] = 0;

        return str;
    }


    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: find()
    // find sub-string from a string.
    // e.g.: a="123456789"; find(a, 0, "456")=3;
    ///////////////////////////////////////////////////////////////////////////
    template <typename TS, typename TC>
    inline int find(TS& str, int pos, const TC* sub)
    {
        int sublen = length(sub);
        if(sublen <= 0) return -1;

        int len = str.length() - sublen;
        const TC* p = *str + max(pos, 0);
        for(int i = max(pos, 0); i <= len; ++i, ++p)
        {
            int j = 0;
            for(j = 0; j < sublen; ++j)
            {
                if(p[j] != sub[j]) break;
            }
            if(sublen <= j)
            {
                return i;
            }
        }

        return -1;
    }

    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: rfind()
    // reverse find sub-string from a string.
    // e.g.: a="123456123"; find(a, -1, "123")=6;
    ///////////////////////////////////////////////////////////////////////////
    template <typename TC>
    inline int rfind(const TC* str, int pos, const TC* sub)
    {
        int sublen = length(sub);
        if(sublen <= 0) return -1;

        int len = length(str) - sublen;
        if(pos >= 0 && pos < len) len = pos;

        const TC* p = str + len;
        for(int i = len; i >= 0; --i, --p)
        {
            int j = 0;
            for(j = 0; j < sublen; ++j)
            {
                if(p[j] != sub[j]) break;
            }
            if(sublen <= j)
            {
                return i;
            }
        }

        return -1;
    }

    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: replace()
    // replace sub-string in a string.
    // e.g.: a="123123123"; replace(a, "12", "ab") = "ab3ab3ab3";
    ///////////////////////////////////////////////////////////////////////////
    template <typename TS, typename TC>
    inline TS replace(TS& str, const TC* oldstr, const TC* newstr)
    {
        TS tmp(str.length() + 256);

        int index = 0, found = 0, len = 0, sublen = length(oldstr), replen = length(newstr);

        while((found = find(str, index, oldstr)) >= 0)
        {
            tmp.resize(len + found - index + replen);
            if(found - index)
            {
                memcpy(*tmp + len, *str + index, (found - index) * sizeof(TC)); 
                len += found - index;
            }
            if(replen)
            {
                memcpy(*tmp + len, newstr, replen * sizeof(TC)); 
                len += replen;
            }

            index = found + sublen;
        }

        if(index < str.length())
        {
            tmp.resize(len + str.length() - index);
            memcpy(*tmp + len, *str + index, (str.length() - index) * sizeof(TC)); 
            len += str.length() - index;
        }

        return tmp;
    }


    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: split()
    // split string by specified splitter character and return the first part.
    // e.g.: a="123 456"; b=split(a, ' '); --> a="456", b="123"
    ///////////////////////////////////////////////////////////////////////////
    template <typename TS, typename TC>
    inline TS split(TS& str, const TC* splitter)
    {
        int splen = length(splitter);
        int len = str.length();
        int n = -1;
        if(splen > 0)
        {
            n = find(str, 0, splitter);
        }
        else
        {
            TC spaces[4][2];
            memset(spaces, 0, sizeof(spaces));
            spaces[0][0] = (TC)0x20;
            spaces[1][0] = (TC)'\t';
            spaces[2][0] = (TC)'\r';
            spaces[3][0] = (TC)'\n';
            for(int i = 0; i < 4; ++i)
            {
                int j = find(str, 0, spaces[i]);
                if(j < 0) continue;
                if(n < 0) n = j;
                else n = min(n, j);
            }
        }

        if(n < 0)
        {
            TS tmp;
            tmp = str;
            str.release();
            return trim(tmp);
        }

        TS tmp(n);
        memcpy(*tmp, *str, n * sizeof(TC));
        n += splen;
        TC* pos = *str + n;
        while(*pos != 0 && *pos <= 0x20) { ++pos; ++n; };
        memmove(*str, pos, (len - n) * sizeof(TC));
        str.resize(len - n);

        return trim(tmp);
    }


    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: atom()
    // get first atom from a string.
    // e.g.: a="123 456"; b="'123 456'789; --> atom(a)="123", atom(b)="'123 456'"
    ///////////////////////////////////////////////////////////////////////////
    template <typename TS>
    inline TS atom(TS& str)
    {
        // get length
        int len = str.length();
        if(len <= 0) { str.resize(0); return TS(0); }

        // skip space
        int n = 0;
        while(n < len && is_space(str[n])) n++;
        if(n >= len) { str.resize(0); return TS(0); }

        // match mark
        int mark_begin[] = {'\'', '"', '(', '{', '['};
        int mark_end[]   = {'\'', '"', ')', '}', ']'};
        int mark = -1, i;
        for(i = 0; i < sizeof(mark_begin) / sizeof(mark_begin[0]); ++ i)
        {
            if(mark_begin[i] == (int)str[n])
            {
                mark = i; 
                break;
            }
        }

        int begin = n++;
        bool next = false;
        while(n < len)
        {
            if(mark >= 0 && str[n] == mark_end[mark])
            {
                n++; 
                if(n < len) for(i = 0; i < sizeof(mark_begin) / sizeof(mark_begin[0]); ++ i)
                {
                    if(mark_begin[i] == (int)str[n])
                    {
                        next = true;
                        break;
                    }
                }
                break; 
            }
            if(mark < 0)
            { 
                if(is_space(str[n])) break; 

                for(i = 0; i < sizeof(mark_begin) / sizeof(mark_begin[0]); ++ i)
                {
                    if(mark_begin[i] == (int)str[n])
                    {
                        next = true;
                        break;
                    }
                }
                if(next) break;
            }
            n++;
        }

        TS tmp = substr(str, begin, n - begin);
        while(n < len && is_space(str[n])) n++;
        for(i = 0; i < len - n; ++i) str[i] = str[n + i];
        str.resize(len - n);

        if(!next) return tmp;
        return tmp + atom(str);
    }


    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: cat()
    // catenate another string at the end of a string.
    // e.g.: a="123" b=456"; cat(a, b); a="123456"
    ///////////////////////////////////////////////////////////////////////////
    template <typename TS, typename TC>
    inline int cat(TS& str, const TC* str2, int n = -1)
    {
        if(!str2) return 0;
        int len = str.length(), len2 = length(str2);
        if(n >= 0) len2 = min(n, len2);
        str.resize(len + len2);
        memcpy((*str) + len, str2, len2 * sizeof(TC));
        return len + len2;
    }

    template <typename TS>
    inline int cat(TS& str, TS &str2)
    {
        return cat(str, *str2);
    }

    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: icmp()
    // compare two string and ignore case.
    // e.g.: icmp("abc", "ABC") = 0
    ///////////////////////////////////////////////////////////////////////////
    template <typename TS, typename TC>
    inline int icmp(TS& str, const TC* str2)
    {
        if(!str2) return (str.length() > 0 ? 1 : 0);
        int len1 = str.length(), len2 = length(str2);
        int len = min(len1, len2);

        const TC* p1 = *str;
        const TC* p2 = str2;
        for(int i = 0; i < len; ++i, ++p1, ++p2)
        {
            if(*p1 != *p2)
            {
                // case comparison
                if(*p1 < 0x40 || *p2 < 0x40 || *p1 > 0x7A || *p2 > 0x7A || abs(*p1 - *p2) != 32)
                {
                    return (*p1 < *p2 ? -1 : 1);
                }
            }
        }

        return (len1 == len2 ? 0 : (len1 < len2 ? -1 : 1));
    }


    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: tolower()
    // convert string to lower case.
    // e.g.: tolower("AbCdEfG") = "abcdefg"
    ///////////////////////////////////////////////////////////////////////////
    template <typename TS>
    inline void tolower(TS& str)
    {
        int len = str.length();

        for(int i = 0; i < len; ++i)
        {
            if(str[i] >= 0x40 && str[i] <= 0x5A)
            {
                str[i] += 32;
            }
        }
    }


    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: encode()
    // encode string avoid the specified character appears.
    ///////////////////////////////////////////////////////////////////////////
#define ESCAPE_CHAR     0x1B
#define SUBTITUTE_CHAR  0x1A
    template <typename TS, typename TC>
    inline TS encode(TS& str, const TC& c)
    {
        int len = str.length();
        TC* src = *str;
        TS tmp;
        tmp.resize(len + 256);
        int count = 0;
        for(int i = 0; i < len; ++i, ++src)
        {
            if(tmp.size() < count + 2) tmp.resize(count + 2);

            if(*src == c)
            {
                tmp[count++] = (TC)ESCAPE_CHAR; 
                tmp[count++] = (TC)SUBTITUTE_CHAR; 
            }
            else if(*src == (TC)ESCAPE_CHAR)
            {
                tmp[count++] = (TC)ESCAPE_CHAR; 
                tmp[count++] = (TC)ESCAPE_CHAR; 
            }
            else 
            {
                tmp[count++] = *src; 
            }
        }

        tmp[count] = 0;

        return tmp;
    }

    ///////////////////////////////////////////////////////////////////////////
    // FUNCTION: decode()
    // encode string avoid the specified character appears.
    ///////////////////////////////////////////////////////////////////////////
    template <typename TS, typename TC>
    inline TS decode(TS& str, const TC& c)
    {
        int len = str.length();
        TC* src = *str;
        TS tmp;
        tmp.resize(len);
        int count = 0;
        for(int i = 0; i < len; ++i, ++src)
        {
            if(*src == (TC)ESCAPE_CHAR)
            {
                i ++;
                src ++;
                if(*src == (TC)SUBTITUTE_CHAR) tmp[count++] = c;
                else tmp[count++] = *src;
            }
            else
            { 
                tmp[count++] = *src; 
            }
        }

        tmp[count] = 0;
        return tmp;
    }


    ///////////////////////////////////////////////////////////////////////////
    // CLASS string: base template class of unicode, utf8 and ansi
    ///////////////////////////////////////////////////////////////////////////
#define STR_GROW_SIZE   256
    template <typename T>
    class string
    {
    public:
        string()                                { discard(); }
        string(int n)                           { discard(); alloc(n); memset(_buffer, 0, _size * sizeof(T)); }
        string(const T* t)                      { discard(); copy(t); }
        string(const string<T>& t)              { discard(); copy(t._buffer); }
        ~string()                               { release(); }

        string<T>&  operator =(string<T>& t)    { release(); _buffer = t._buffer; _size = t._size; t.discard(); return *this; }
        string<T>&  operator =(const T* t)      { release(); copy(t); return *this; }
        T*          operator *()                { return _buffer ? _buffer : &_null; }
        T&          operator [](int n)          { return (n > _size && _buffer) ? _null : _buffer[n]; }

        bool        operator ==(const T* t)     { int len = length(); if(len != STRING::length(t)) return false; const T *p1=_buffer, *p2=t; for(;len>0;len--,p1++,p2++) if(*p1 != *p2) return false; return true;}
        bool        operator ==(string<T>& t)   { return *this == *t; }
        bool        operator !=(const T* t)     { return !(*this == t); }
        bool        operator !=(string<T>& t)   { return !(*this == *t); }

        int         size()                      { return _size; }
        bool        is_null()                   { return _buffer == NULL; }
        bool        is_empty()                  { return length() == 0; }
        int         length()                    { return STRING::length(_buffer); }

        void        alloc(int n)                { if(_size >= n && _buffer) return; release(); _size = n; _buffer = new T[_size + 1]; memset(_buffer+_size,0,sizeof(T)); }
        void        discard()                   { _buffer = NULL; _size = 0; memset(&_null, 0, sizeof(T)); }
        void        release()                   { if(_buffer) delete [] _buffer; discard(); }
        void        copy(const T* t)            { if(!t)return; int len = STRING::length(t); if(_size < len) { release(); _size = len; _buffer = new T[_size + 1]; memset(_buffer+_size,0,sizeof(T)); } memcpy(_buffer, t, sizeof(T) * len); }

        void        resize(int n)               { if(_size < n || !_buffer) { string<T> t((1+n/STR_GROW_SIZE)*STR_GROW_SIZE); if(_size)memcpy(t._buffer, _buffer, _size * sizeof(T)); *this = t; } memset(_buffer+n, 0, sizeof(T)); }

    protected:
        T*      _buffer;
        int     _size;
        T       _null;
    };


    class ansi;
    class utf8;
    class unicode;


    ///////////////////////////////////////////////////////////////////////////
    // CLASS unicode: string consist of wide characters
    ///////////////////////////////////////////////////////////////////////////
    class unicode : public string<wchar_t>
    {
    public:
        unicode() : string<wchar_t>()           {}
        unicode(int n) : string<wchar_t>(n)     {}
        unicode(const char* t);
        unicode(const wchar_t* t) : string<wchar_t>(t){}
        unicode(const unicode& t) : string<wchar_t>(t){}
        unicode&  operator =(const wchar_t* t)  { release(); copy(t); return *this; }
        unicode&  operator =(unicode& t)        { release(); _buffer = t._buffer; _size = t._size; t.discard(); return *this; }
        unicode   operator +(const wchar_t* t)  { int l1 = length(), l2 = STRING::length(t); unicode r(l1+l2); memcpy(*r, _buffer, l1*sizeof(wchar_t)); memcpy(*r+l1, t, l2*sizeof(wchar_t)); return r; }
        unicode   operator +(unicode& t)        { int l1 = length(), l2 = t.length(); unicode r(l1+l2); memcpy(*r, _buffer, l1*sizeof(wchar_t)); memcpy(*r+l1, *t, l2*sizeof(wchar_t)); return r; }

        unicode(ansi& t) : string<wchar_t>()    { *this = t; }
        unicode(utf8& t) : string<wchar_t>()    { *this = t; }
        unicode&  operator =(ansi& t);
        unicode&  operator =(utf8& t);
    };


    ///////////////////////////////////////////////////////////////////////////
    // CLASS ansi: string consist of ascii characters
    ///////////////////////////////////////////////////////////////////////////
    class ansi : public string<char>
    {
    public:
        ansi() :  string<char>()                {}
        ansi(int n) : string<char>(n)           {}
        ansi(const char* t) : string<char>(t)   {}
        ansi(const wchar_t* t);
        ansi(const ansi& t) : string<char>(t)   {}

        ansi&  operator =(const char* t)        { release(); copy(t); return *this; }
        ansi&  operator =(ansi& t)              { release(); _buffer = t._buffer; _size = t._size; t.discard(); return *this; }
        ansi   operator +(const char* t)        { int l1 = length(), l2 = STRING::length(t); ansi r(l1+l2); memcpy(*r, _buffer, l1); memcpy(*r+l1, t, l2); return r; }
        ansi   operator +(ansi& t)              { int l1 = length(), l2 = t.length(); ansi r(l1+l2); memcpy(*r, _buffer, l1); memcpy(*r+l1, *t, l2); return r; }        

        ansi(utf8& t) : string<char>()          { *this = t; }
        ansi(unicode& t) : string<char>()       { *this = t; }
        ansi&  operator =(utf8& t)              { unicode u; u = t; return *this = u; }
        ansi&  operator =(unicode& t)           { ansi a(*t); return *this = a; }
    };


    ///////////////////////////////////////////////////////////////////////////
    // CLASS utf8: string consist of utf8 characters
    ///////////////////////////////////////////////////////////////////////////
    class utf8 : public string<char>
    {
    public:
        utf8() :  string<char>()                {}
        utf8(int n) : string<char>(n)           {}
        utf8(const char* t) : string<char>(t)   {}
        utf8(const wchar_t* t);
        utf8(const utf8& t) : string<char>(t)   {}

        utf8&  operator =(const char* t)        { release(); copy(t); return *this; }
        utf8&  operator =(utf8& t)              { release(); _buffer = t._buffer; _size = t._size; t.discard(); return *this; }
        utf8   operator +(const char* t)        { int l1 = length(), l2 = STRING::length(t); utf8 r(l1+l2); memcpy(*r, _buffer, l1); memcpy(*r+l1, t, l2); return r; }
        utf8   operator +(utf8& t)              { int l1 = length(), l2 = t.length(); utf8 r(l1+l2); memcpy(*r, _buffer, l1); memcpy(*r+l1, *t, l2); return r; }

        utf8(ansi& t) : string<char>()          { *this = t; }
        utf8(unicode& t) : string<char>()       { *this = t; }
        utf8&  operator =(ansi& t)              { unicode u(t); return *this = u; }
        utf8&  operator =(unicode& t)           { utf8 u(*t); return *this = u; }
    };



}




#define VECTOR_GROW_SIZE    1024

// ============================================================================
// CLASS gap_vector: vector container with a gap and divide the content into
// two parts. different from traditional vector, gap_vector accelerates the 
// insert and delete operations at the gap position.
// ============================================================================
template <typename T>
class gap_vector
{
public:
    gap_vector() : _head(NULL), _body(NULL), _body_size(0), _grow_size(VECTOR_GROW_SIZE)
    {
        clear();
    }

    ~gap_vector()
    {
        clear();
        if(_head)
        {
            delete [] _head;
            _head = NULL;
            _body = NULL;
        }
    }

    // FUNCTION clear(): clear vector without changing the buffer size
    void clear()
    {
        _len_before_gap = 0;
        _len_after_gap = 0;
        _len_content = 0;
        _len_gap = 0;
        _gap_pos = 0;
    }

    // FUNCTION set_grow_size(): modify auto-growth size of the buffer
    void set_grow_size(int grow_size)
    {
        _grow_size = max(1, grow_size);
    }

    // FUNCTION resize_buffer(): resize the buffer
    bool resize_buffer(int size)
    {
        if(size > _body_size)
        {
            T* new_body = new T [size + 1];
            if(NULL == new_body)
            {
                return false;
            }
            memcpy(new_body + 1, _body, _body_size * sizeof(T));
            _body_size = size;
            delete [] _head;
            _head = new_body;
            _body = _head + 1;
        }
        return true;
    }

    // FUNCTION resize(): resize the vector
    bool resize(int size)
    {
        // extend at the end of content
        gap_at(_len_content, size - _len_content);
        _len_before_gap += size - _len_content;
        _len_gap -= size - _len_content;
        _len_content += size - _len_content;
        return true;
    }

    // FUNCTION gap_at(): move the gap position
    bool gap_at(int pos, int room)
    {
        // grow size when no enough room
        while(room + _len_content > _body_size)
        {
            if(!resize_buffer(_body_size + _grow_size))
            {
                return false;
            }
        }

        // right gap position and enough room
        if(_len_before_gap == pos && _len_gap >= room)
        {
            return true;
        }

        // adjust gap position in case of no enough space or reach the end
        // |BBBBBB  AAAAAA              |   =>  |BBBBBB        AAAAAA        |
        // |BBBBBB                AAAAAA|   =>  |BBBBBB        AAAAAA        |
        if(_len_gap < room || _len_after_gap + _gap_pos == _body_size)
        {
            // new _gap_pos = _len_before_gap + room + (_body_size - _len_before_gap - room - _len_after_gap) / 2
            int new_gap_pos = (_body_size + _len_before_gap + room - _len_after_gap) / 2;
            if(new_gap_pos + _len_after_gap > _body_size) { return false; } // not enough room
            if(new_gap_pos != _gap_pos)
            {
                memmove(_body + new_gap_pos, _body + _gap_pos, (_len_after_gap) * sizeof(T));
                _gap_pos = new_gap_pos;
                _len_gap = _gap_pos - _len_before_gap;
            }
        }

        // BBB*BBB    AAAAAA  =>   BBB    BBBAAAAAA
        if(pos < _len_before_gap)
        {
            memmove(_body + _gap_pos - _len_before_gap + pos, _body + pos, (_len_before_gap - pos) * sizeof(T));
        }
        // BBBBBB    AAA*AAA  =>  BBBBBBAAA    AAA
        else
        {
            memmove(_body + _len_before_gap, _body + _gap_pos, (pos - _len_before_gap) * sizeof(T));
        }
        _len_before_gap = pos;
        _len_after_gap = _len_content - pos;
        _gap_pos = pos + _len_gap;
        return true;
    }

    // FUNCTION insert(): insert content to pos
    bool insert(int pos, T* pt, int size)
    {
        // insert at the end and with enough room
        if(pos == _len_content && _len_gap + _len_content + size <= _body_size)
        {
            memcpy(_body + _len_gap + _len_content, pt, size * sizeof(T));
            _len_content += size;
            _len_after_gap += size;
            return true;
        }

        // move gap and ensure enough room for new cells
        if(!gap_at(pos, size))
        {
            return false;
        }

        // insert at pos
        memcpy(_body + pos, pt, size * sizeof(T));
        _len_before_gap += size;
        _len_content += size;
        _len_gap -= size;
        return true;
    }

    // FUNCTION remove(): remove content from pos
    void remove(int pos, int length = 1)
    {
        int remove_len = max(0, min(_len_content - pos, length));

        if(!gap_at(pos + remove_len, 0))
        {
            return;
        }

        _len_before_gap -= remove_len;
        _len_content -= remove_len;
        _len_gap += remove_len;
    }

    // OPERATOR =: copy content from source vector
    void operator = (gap_vector<T> &src)
    {
        clear();
        set_buffer_size(src.length());

        for(int i = 0; i < src.length(); ++i)
        {
            insert(i, &src[i], 1);
        }
    }

    inline int  buffer_size()       { return _body_size; }      // get buffer size
    inline int  length()            { return _len_content; }    // get vector length
    inline T&   back()              { return _len_content == _len_before_gap ? _body[_len_content - 1] : _body[_len_content + _len_gap - 1]; }  // get last cell
    inline bool push_back(T& t)     { return insert(_len_content, &t, 1); }         // push cell to the end
    inline T& operator [] (int n)   { if(n<0||n>=_body_size)return *(_head); if(n<_len_before_gap)return *(_body+n); else return *(_body+n+_len_gap); }

    /*
    std::string debug_info()
    {
        std::string tmpstr;
        char buf[1024];
        sprintf_s(buf, "_body_size=%d, _len_content=%d, _len_before_gap=%d:\n", _body_size, _len_content, _len_before_gap);
        tmpstr += buf;

        for(int i = 0; i < _len_before_gap; ++i)
        {
            sprintf_s(buf, "<%c>.%02X ", _body[i] < 0x20 ? '?' : _body[i], _body[i]);
            tmpstr += buf;
            if(i % 10 == 9)
            {
                tmpstr += "\n";
            }
        }

        sprintf_s(buf, "\n_len_gap=%d, _gap_pos=%d, _len_after_gap=%d:\n", _len_gap, _gap_pos, _len_after_gap);
        tmpstr += buf;
        for(int i = 0; i < _len_after_gap; ++i)
        {
            sprintf_s(buf, "<%c>.%02X ", _body[i + _gap_pos] < 0x20 ? '?' : _body[i + _gap_pos], _body[i + _gap_pos]);
            tmpstr += buf;
            if(i % 10 == 9)
            {
                tmpstr += "\n";
            }
        }
        tmpstr += "\n";

        if(_len_content != _len_before_gap + _len_after_gap)
        {
            tmpstr += "Invalid _len_content!!!\n";
        }

        if(_len_gap != _gap_pos - _len_before_gap)
        {
            tmpstr += "Invalid _len_gap!!!\n";
        }

        return tmpstr;
    }
*/
private:
    T           *_head, *_body;         // head point of vector buffer
    int         _body_size;             // current buffer size
    int         _grow_size;             // vector buffer growth size
    int         _len_before_gap;        // text is devided into two parts by the gap, this is the length of first part
    int         _len_after_gap;         // text is devided into two parts by the gap, this is the length of second part
    int         _gap_pos;               // gap end position

    int         _len_content;           // _len_content = _len_before_gap + _len_after_gap
    int         _len_gap;               // _len_gap = _gap_pos - _len_before_gap
};




// ============================================================================
// CLASS data_vector: vector for non-object data
// vector container with a cursor, data changed at head or tail of the vector 
// will not cause the memory data moving. Cursor will reset when vector is 
// empty or size not enough.
// ============================================================================
template <typename T>
class data_vector
{
public:
    explicit data_vector() : _head(NULL), _cursor(NULL), _size(0), _length(0) {}
    ~data_vector()                      { release(); }

    inline T*   operator *()            { return _cursor; }
    inline T*   tail()                  { return _cursor ? (_cursor + _length) : NULL; }
    inline int  length()                { return _length; }
    inline int  gap()                   { return (_cursor - _head); }
    inline int  room()                  { return _size - _length - (_cursor - _head); }
    inline T&   operator [] (int n)     { if(n<0||n>=_length)return _head[_size + 1]; return _cursor[n]; }
    inline T&   back()                  { return _length ? _cursor[_length - 1] : _head[_size + 1]; }

    inline void clear()                 { _length = 0; _cursor = _head; if(_cursor)_zero(0); }
    inline void release()               { if(_head) delete [] _head; _cursor = _head = NULL; _size = _length = 0; } 
    inline void resize(int n)           { if(n<0)return; int len = min(_length, n); T* t = new T[n + 2]; for(int i = 0; i < len; ++i) t[i] = _cursor[i]; release(); _cursor = t; _head = t; _length = len; _size = n; _zero(len); }
    inline void make_room(int n)        { if(room() < n) resize( (1 + ( _length + n) / VECTOR_GROW_SIZE ) * VECTOR_GROW_SIZE ); }
    inline void extend(int n)           { _length += max(0, min(n, room())); _zero(_length); }

    inline int  push_front(const T t)   { if(_cursor == _head) { make_room(1); _move(1, 0, _length); } else _cursor --; _length ++; *_cursor=t; _zero(_length); return 0; }
    inline int  push_back(const T t)    { make_room(1); *tail() = t; _length++; _zero(_length); return _length - 1; }
    inline void pop_front(int n = 1)    { if(n >= _length) clear(); else if(n > 0) { _length -= n; _cursor += n; } }
    inline void pop_back(int n = 1)     { if(n >= _length) clear(); else if(n > 0) { _length -= n; } _zero(_length); }
    inline void insert(int n, const T t){ if(n < 0 || n >= _length) return; make_room(1); _move(n + 1, n, _length - n); _cursor[n]=t; _length++; }
    inline void remove(int n)           { if(n < 0 || n >= _length) return; _move(n, n + 1, _length - n); _length--; }

private:
    inline void _zero(int n)            { memset(_cursor + n, 0, sizeof(T)); }
    inline void _move(int d, int s, int l) { if(d<s) { T *t=_cursor+d; T *o=_cursor+s; for(int i=0; i<l; ++i,++t,++o) *t = *o; } else { T *t=_cursor+d+l-1; T *o=_cursor+s+l-1; for(int i=l;i>0;--i,--t,--o) *t = *o; } }
    T           *_head, *_cursor;
    int         _size, _length;
};



// ============================================================================
// CLASS obj_vector: vector for object
// vector pointer is not available in obj_vector.
// ============================================================================
template <typename T>
class obj_vector
{
public:
    obj_vector()                        {}
    ~obj_vector()                       { release(); }

    inline bool valid(int n)            { return (n >= 0 && n < _data.length()); }
    inline int  length()                { return _data.length(); }
    inline T&   operator [] (int n)     { if(n < 0 || n > _data.length()) return _null; return *_data[n]; }


    inline int  create()
    {
        T* t = new T;
        if(_free.length() && valid(_free.back()))
        {
            int n = _free.back();
            if(_data[n]) delete _data[n];
            _data[n] = t;
            _free.pop_back();
            return n;
        }
        _data.push_back(t);
        return _data.length() - 1;
    }
    inline void remove(int n)           { if(n < 0 || n >= _data.length() || !_data[n]) return; delete _data[n]; _data[n] = NULL; _free.push_back(n); }
    inline void pop_front()             { if(_data.length() <= 0 || !_data[0]) return; delete _data[0]; _data[0] = NULL; _data.pop_front(); }
    inline void pop_back()              { if(_data.length() <= 0 || !_data[_data.length()-1]) return; delete _data[_data.length()-1]; _data[_data.length()-1] = NULL; _data.pop_back(); }

    inline void release()               { for(int i=0;i<_data.length();++i) if(_data[i]) { delete _data[i]; _data[i] = NULL; } _data.release(); }

protected:
    data_vector<T*>                     _data;
    data_vector<int>                    _free;
    T                                   _null;
};



// ============================================================================
// CLASS unicode_index: unicode string vector with index feature
// element could be accessed by string of sequence.
// ============================================================================
class unicode_index
{
public:
    unicode_index()                         {}
    ~unicode_index()                        { release(); }

    inline void release()                   { _name.release(); _index.clear(); }
    inline int  length()                    { return _name.length(); }
    inline int  create(const wchar_t* n)    { int idx = _name.length(); _name.create(); _name[idx] = n; STRING::unicode l(n); STRING::tolower(l); _index[*l] = idx; return idx; }
    inline int  find(const wchar_t* n)      { if(!n) return -1; STRING::unicode l(n); STRING::tolower(l); _iter = _index.find(*l); return (_iter == _index.end() ? -1 : _iter->second); }
    inline void remove(int n)               
    {
        if(n < 0 || n >= _name.length()) return;
        STRING::unicode l(*_name[n]); 
        STRING::tolower(l); 
        _index.erase(*l); 
        _name.remove(n); 
    }
    inline void pop_front()                 { if(_name.length() <= 0) return; _index.erase(*_name[0]); _name.remove(0); }
    inline void pop_back()                  { if(_name.length() <= 0) return; _index.erase(*_name[_name.length() - 1]); _name.remove(_name.length() - 1); }
    inline const wchar_t* operator [](int n){ return *_name[n]; }

private:
    std::map<std::wstring, int>             _index;
    std::map<std::wstring, int>::iterator   _iter;
    obj_vector<STRING::unicode>             _name;
};


// ============================================================================
// CLASS map_vector: object vector with name mapping
// case insensitive of the object name.
// ============================================================================
template <typename T>
class map_vector: public obj_vector<T>
{
public:
    map_vector()                        {}
    ~map_vector()                       { release(); }

    inline T&   operator [] (int n)     { if(n < 0 || n > _data.length()) return _null; return *_data[n]; }
    inline T&   operator [] (const wchar_t* n)  { return (*this)[_index.find(n)]; }

    inline int  create(const wchar_t* n){ int i = find(n); if(i>=0) return i; obj_vector::create(); _index.create(n); return _data.length() - 1; }
    inline void remove(int n)           { obj_vector::remove(n); _index.remove(n); }
    inline void remove(const wchar_t* n){ int index = find(n); obj_vector::remove(index); _index.remove(index); }
    inline void pop_front()             { if(_data.length() <= 0 || !_data[0]) return; delete _data[0]; _data[0] = NULL; _data.pop_front(); _index.pop_front(); }
    inline void pop_back()              { if(_data.length() <= 0 || !_data[_data.length()-1]) return; delete _data[_data.length()-1]; _data[_data.length()-1] = NULL; _data.pop_back(); _index.pop_back(); }
    inline const wchar_t* name(int n)   { return _index[n]; }

    inline void release()               { for(int i=0;i<_data.length();++i) if(_data[i]) { delete _data[i]; _data[i] = NULL; } _data.release(); _index.release(); }
    inline int  find(const wchar_t* n)  { return (n && *n) ? _index.find(n) : -1; }

protected:
    unicode_index                       _index;
};



// ============================================================================
// CLASS pipe: FIFO object queue with multi-threads protection
// ============================================================================
template <typename T>
class pipe
{
public:
    pipe()                      { _hmutex = CreateMutex(NULL, FALSE, NULL); _hevent = CreateEvent(NULL, TRUE, FALSE, NULL); }
    ~pipe()                     { CloseHandle(_hmutex); CloseHandle(_hevent);}

    inline void lock()          { WaitForSingleObject(_hmutex, INFINITE); }
    inline void unlock()        { ReleaseMutex(_hmutex); }
    inline void pop(T* t)       { lock(); if(t)*t = _pipe.front(); _pipe.pop_front(); unlock();}
    inline void push(T t)       { lock(); _pipe.push_back(t); unlock(); SetEvent(_hevent); }
    inline void push_front(T t) { lock(); _pipe.push_front(t); unlock(); SetEvent(_hevent); }
    inline int  count()         { return (int)_pipe.size(); }
    inline bool wait(DWORD t)   { if(WaitForSingleObject(_hevent, t) != WAIT_OBJECT_0) return false; ResetEvent(_hevent); return true; }

private:
    HANDLE                      _hmutex, _hevent;
    std::list<T>                _pipe;
};


class var
{
public:
    var()                       { _integer = 0; _utf8 = ""; _converted = false; _is_int = false; }
    ~var()                      {}
    var(const var& v)           { STRING::utf8 tmp(v._utf8); _utf8 = tmp; _integer = v._integer; }
    var& operator = (var& v)    { _utf8.copy(*v._utf8); _integer = v._integer; return *this; }

    inline void set(int i)                                 { _integer = i; _converted = false; _is_int = true; }
    inline void set(const char* s)                         { _utf8 = s; _converted = false; _is_int = false; }
    inline int& operator = (int i)                         { set(i); return _integer; }
    inline STRING::utf8& operator = (STRING::utf8& a)      { set(*a); return _utf8; }
    inline STRING::utf8& operator = (const char* s)        { set(s); return _utf8; }
    
    inline const char*  utf8()  { if(_is_int && !_converted) _to_string(); return *_utf8; }
    inline const int integer()  { if(!_is_int && !_converted) _to_int(); return _integer; }
    inline bool     is_int()    { return _is_int; }
    inline bool     is_string() { return !_is_int; }

private:
    inline void _to_int()       { _integer = atoi(*_utf8); _converted = true; }
    inline void _to_string()    { _utf8.resize(64); _itoa_s(_integer, *_utf8, 64, 10); _converted = true; }

    int                         _integer;
    STRING::utf8                _utf8;
    bool                        _is_int, _converted;
};



class timer
{
public:
    timer()                     { _tick_count = _tick_now = GetTickCount(); }
    timer(int n)                { _tick_count = _tick_now = GetTickCount(); set_timer(n); }
    ~timer()                    {}

    void    set_timer(int n)    { _timer = DWORD(n); }
    bool    tick()              { _tick_now = GetTickCount(); if(_timer == 0) return true; bool t = false; while(_tick_now >= _timer + _tick_count) { t = true; _tick_count += _timer; } return t; }
    void    sleep()             { if(tick()) return; Sleep(_tick_count + _timer - _tick_now); tick(); }
    int     count_down()        { _tick_now = GetTickCount(); return (_tick_count + _timer < _tick_now) ? 0 : _tick_count + _timer - _tick_now; }

private:
    DWORD                       _tick_count, _tick_now;
    DWORD                       _timer;
};


// ============================================================================
// namespace::H2APP
// utilities functions of H2 application framework.
// ============================================================================
namespace H2APP
{
    typedef pipe<STRING::unicode>   BUS;
    typedef map_vector<var>         SESSION;
    
    extern map_vector<BUS>          bus;                                                    // System BUS
    extern map_vector<SESSION>      data;                                                   // Global data
    bool                            send_msg(const wchar_t* wmsg);                          // send bus message
    void                            pack_msg(STRING::unicode& msg, const wchar_t* tag);     // pack tag to a bus message
    STRING::unicode                 unpack_msg(STRING::unicode& msg);                       // strip last tag from a bus message

    // Application Environment
    STRING::unicode app_path();                                                             // application path
    STRING::unicode app_name();                                                             // application name
    STRING::unicode time_stamp(const wchar_t* format = L"%Y-%m-%d %H:%M:%S");               //time

    // File Access
    unsigned long                   file_size(STRING::unicode filename);                    // Check file size    
    STRING::unicode                 load_file(STRING::unicode filename);                    // Load text file
    bool                            write_file(STRING::unicode filename, const char* txt);  // Write text file
    bool                            file_exist(STRING::unicode filename);                   // Check file existance
};
